package yz.com.javautil.astar;

import java.util.ArrayList;
import java.util.List;

/**
 * A星寻路算法
 * 参考资料：
 * https://www.cnblogs.com/technology/archive/2011/05/26/2058842.html
 * https://www.redblobgames.com/pathfinding/a-star/introduction.html
 *
 * @author Administrator
 */
public class AStarSearch {

    /**
     * 开启列表和关闭列表
     */
    private List<AStarNode> openList = new ArrayList<>(), closeList = new ArrayList<>();

    /**
     * 获取G值
     * 从起点沿着产生的路径，移动到网格上指定节点的移动消耗。
     *
     * @param currentAStarNode：当前节点
     * @return 移动消耗
     */
    private double getG(AStarNode currentAStarNode) {
        if (currentAStarNode.getFromAStarNode() != null) {
            //判断当前节点与其父节点之间的位置关系（水平上下或对角线）
            if (currentAStarNode.getX() == currentAStarNode.getFromAStarNode().getX() || currentAStarNode.getY() == currentAStarNode.getFromAStarNode().getY()) {
                return currentAStarNode.getG() + 10;
            }
            return currentAStarNode.getG() + 14;
        }
        return currentAStarNode.getG();
    }

    /**
     * 获取H值
     * 从当前格移动到终点的预估移动消耗
     *
     * @param currentAStarNode：当前节点
     * @param endAStarNode：终点
     * @return 预估消耗
     */
    private double getH(AStarNode currentAStarNode, AStarNode endAStarNode) {
        return (Math.abs(currentAStarNode.getX() - endAStarNode.getX()) + Math.abs(currentAStarNode.getY() - endAStarNode.getY())) * 10;
    }

    /**
     * 获取F值
     * F = G + H
     *
     * @param currentAStarNode 当前节点
     * @return G+H
     */
    private double getF(AStarNode currentAStarNode) {
        return currentAStarNode.getG() + currentAStarNode.getH();
    }

    /**
     * 将选中节点周围的节点添加进“开启列表”
     *
     * @param AStarNode 选中的节点
     * @param AStarGrid  地图数据
     */
    private void inOpen(AStarNode AStarNode, AStarGrid AStarGrid) {
        int x = AStarNode.getX();
        int y = AStarNode.getY();
        int moveInt = 3;
        for (int i = 0; i < moveInt; i++) {
            for (int j = 0; j < moveInt; j++) {
                // 判断条件为： 1.节点为可到达的（即不是障碍物，不在关闭列表中） 2.开启列表中不包含 3.不是选中节点
                boolean reachable = AStarGrid.getMap()[x - 1 + i][y - 1 + j].isReachable();
                boolean notContains = !openList.contains(AStarGrid.getMap()[x - 1 + i][y - 1 + j]);
                boolean notSelf = !(x == (x - 1 + i) && y == (y - 1 + j));
                if (reachable && notContains && notSelf) {
                    AStarGrid.getMap()[x - 1 + i][y - 1 + j].setFromAStarNode(AStarGrid.getMap()[x][y]);
                    // 将选中节点作为父节点
                    AStarGrid.getMap()[x - 1 + i][y - 1 + j].setG(getG(AStarGrid.getMap()[x - 1 + i][y - 1 + j]));
                    AStarGrid.getMap()[x - 1 + i][y - 1 + j].setH(getH(AStarGrid.getMap()[x - 1 + i][y - 1 + j], AStarGrid.getEndAStarNode()));
                    AStarGrid.getMap()[x - 1 + i][y - 1 + j].setF(getF(AStarGrid.getMap()[x - 1 + i][y - 1 + j]));
                    openList.add(AStarGrid.getMap()[x - 1 + i][y - 1 + j]);
                }
            }
        }
    }

    /**
     * 使用冒泡排序将开启列表中的节点按F值从小到大排序
     *
     * @param AStarNodeList 待排序的节点列表
     */
    private void sortListByF(List<AStarNode> AStarNodeList) {
        for (int i = 0; i < AStarNodeList.size() - 1; i++) {
            for (int j = i + 1; j < AStarNodeList.size(); j++) {
                if (AStarNodeList.get(i).getF() > AStarNodeList.get(j).getF()) {
                    AStarNode tmp = AStarNodeList.get(i);
                    AStarNodeList.set(i, AStarNodeList.get(j));
                    AStarNodeList.set(j, tmp);
                }
            }
        }
    }

    /**
     * 将节点添加进”关闭列表“
     *
     * @param AStarNode     当前节点
     * @param openList 开启列表
     */
    private void inClose(AStarNode AStarNode, List<AStarNode> openList) {
        if (openList.contains(AStarNode)) {
            // 设置为不可达
            AStarNode.setReachable(false);
            openList.remove(AStarNode);
            closeList.add(AStarNode);
        }
    }

    /**
     * 寻路算法
     *
     * @param AStarGrid 地图
     */
    public void search(AStarGrid AStarGrid) {
        // 对起点即起点周围的节点进行操作
        inOpen(AStarGrid.getMap()[AStarGrid.getStartAStarNode().getX()][AStarGrid.getStartAStarNode().getY()], AStarGrid);
        // 将起点放入关闭列表并设置为不可达且将startNode的fromNode设置为自己
        closeList.add(AStarGrid.getMap()[AStarGrid.getStartAStarNode().getX()][AStarGrid.getStartAStarNode().getY()]);
        AStarGrid.getMap()[AStarGrid.getStartAStarNode().getX()][AStarGrid.getStartAStarNode().getY()].setReachable(false);
        AStarGrid.getMap()[AStarGrid.getStartAStarNode().getX()][AStarGrid.getStartAStarNode().getY()].setFromAStarNode(AStarGrid.getMap()[AStarGrid.getStartAStarNode().getX()][AStarGrid.getStartAStarNode().getY()]);
        // 根据F值进行排序
        sortListByF(openList);
        // 重复步骤 直到开启列表中包含终点时 循环退出
        do {
            // 将最小F值的节点当作起点重复步骤
            AStarNode AStarNodeOfMinF = openList.get(0);
            inOpen(AStarNodeOfMinF, AStarGrid);
            inClose(AStarNodeOfMinF, openList);
            sortListByF(openList);
        } while (!openList.contains(AStarGrid.getMap()[AStarGrid.getEndAStarNode().getX()][AStarGrid.getEndAStarNode().getY()]));
        // 将终点放入关闭列表
        inClose(AStarGrid.getMap()[AStarGrid.getEndAStarNode().getX()][AStarGrid.getEndAStarNode().getY()], openList);
        // 将路径标记出来
        showPath(closeList, AStarGrid);
    }

    /**
     * 将路径标记出来
     *
     * @param AStarNodeList 路径节点
     * @param AStarGrid      地图数据
     */
    public void showPath(List<AStarNode> AStarNodeList, AStarGrid AStarGrid) {
        // 从终点开始回溯到起点
        if (AStarNodeList.size() > 0) {
//            Node node = map.getMap()[map.getEndNode().getX()][map.getEndNode().getY()];
            AStarNode AStarNode = AStarGrid.getEndAStarNode();
            while (!(AStarNode.getX() == AStarGrid.getStartAStarNode().getX() && AStarNode.getY() == AStarGrid.getStartAStarNode().getY())) {
                AStarNode.getFromAStarNode().setValue("*");
                AStarNode = AStarNode.getFromAStarNode();
            }
        }
        AStarGrid.getMap()[AStarGrid.getStartAStarNode().getX()][AStarGrid.getStartAStarNode().getY()].setValue("A");
    }

}
